import java.util.Arrays;

public class HeapTest {
	private int [] elem;
	private int usedSize;

	public HeapTest() {
		this.elem = new int [10];
	}
	public void initHeap(int [] array) {
		for(int i=0;i<array.length;i++) {
			elem[i]=array[i];
			this.usedSize++;
		}
	}
	public  void createHeapDown( ) {
		for(int parent=(usedSize-2)/2;parent>=0;parent--) {
			adjustDown(parent,usedSize);//向下调整的最坏情况下的时间复杂度为logN,以二为底的。
		}
	}
	//向下调整
	//时间复杂度为每一层的节点乘以每个节点的最坏情况下向下移动的次数
	//算出来是一个等比数列，时间复杂度通过二叉树的高度代换，然后关于一个节点的数量的关系式
	//建堆的时间复杂度为O(N)
	private void adjustDown(int parent, int usedSize) {
		int child=parent*2+1;
		while(child<usedSize) {
			if(child+1<usedSize&&this.elem[child]<this.elem[child+1]) {
				child++;
			}
			if(elem[parent]<elem[child]) {
				//小的话直接直接进行交换
				swap(parent, child);
				//在这里的同时还要观察孩子节点下面还有没有
				parent = child;
				child = parent * 2 + 1;
			} else {
				//已经是大根堆了
				break;
			}
		}
	}
	public void swap(int parent,int child) {
		int temp=elem[parent];
		elem[parent]=elem[child];
		elem[child]=temp;
	}
	public void display() {
		for(int i = 0; i<this.elem.length;i++) {
			System.out.print(elem[i]+" ");
		}
		System.out.println();
	}

	/**
	 * 在堆中进行插入元素
	 *
	 * @param val
	 */
	public void offer(int val) {
		if(isFull()) {
			this.elem= Arrays.copyOf(this.elem,this.elem.length*2);
		}
		//直接在最后面的位置进行插入
		this.elem[usedSize]=val;
		adjustUp(usedSize);
		usedSize++;
	}

	/**
	 * 向上调整主要针对插入元素时方法
	 * @param child
	 */
	private void adjustUp(int child) {
		int parent=(child-1)/2;
		while(child>0) {
			//此时堆已经建好了，但是由于一个节点的插入，我们需要进行改变这个节点的位置
			//向下调整建堆的时候是大根堆
			if(elem[parent]<elem[child]) {
				swap(parent,child);
				child=parent;
				parent=(child-1)/2;
			}
			else {
				break;
			}
		}
	}
	public boolean isFull() {
		return this.usedSize==this.elem.length;
	}

	/**
	 * 删除堆顶的元素,并没有真正的删除,先将堆顶的元素交换下来
	 * @return
	 */
	public int poll() {
		int temp=this.elem[0];
		swap(0,usedSize-1);
		usedSize--;
		adjustDown(0,usedSize);
		return temp;
	}

	/**
	 * 堆排序，升序是先建大堆，然后依次交换，再进行向下调整，降序反过来
	 * 为什么要建大堆呢，因为建大堆保证后面有序
	 */
	public void heapSort() {
		int end=usedSize-1;
		while(end>0) {
			swap(0,end);
			adjustDown(0,end);
			end--;
		}
	}
}
